<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>快速排序</title>
</head>
<body>
    <script>
        /** 快速排序
         * 
         * 工作原理：原则一个基准数(中心值 pivot)，开启一个循环，小于 pivot 的值放入到 left，大于 pivot 的值放入的 right。对 left 和 right 进行递归
         * 
         * 实现思路
         * 1.使用递归
         * 2.如果数组length < 2，返回数组
         * 3.用Math。floor计算出中心点的下标值
         * 4.使用 reduce 和 push，将数组分成两个数组，一个是包含小于pivot的值和等于 pivot的值。另一个是包含大于pivot的值
         * 5.对创建的子数组，递归调用quickSort，
        */

        /**
         * 时间复杂度 最好情况 O(n*logn) 每次分成相同长度的两个数组   最坏情况: O(n2)   每次分成0 和 n-1
         * 
         * 参考   https://zhuanlan.zhihu.com/p/341201904
        */

        let arr1 = [1, 2, 8, 7, 3, 6, 4, 5, 9, 1, 2];

        const quickSort = (arr) => {
            if(!Array.isArray(arr)) return [];
            const length = arr.length
            if(length < 2) return arr;
            let pivotIndex = Math.floor(length / 2);
            let pivot = arr[pivotIndex] // 中心点
            
            // 第一种写法
           let [left, right] = arr.reduce((accout, item, i) =>{
                if(item < pivot || (item === pivot && i !== pivotIndex)) {
                    accout[0].push(item)
                }else if( item > pivot) {
                    accout[1].push(item)
                }
                return accout
           }, [[], []])

            // 第二种写法
            // let left = []
            // let right = []
            // for (let i = 0; i < length; i++) {
            //     const item = arr[i];
            //     if(item < pivot || (item === pivot && i !== pivotIndex)) {
            //         left.push(item)
            //     } else if(item > pivot) {
            //         right.push(item)
            //     }
            // }

            // 第三种写法
            return [...quickSort(left), pivot, ...quickSort(right)]
        }

        // 测试
        const result = quickSort(arr1)
        console.log('快速排序结果:  ', result)

    </script>
</body>
</html>